1. Field of the Invention
The present invention relates to an apparatus and method for conducting an electronic recurring auction in which time limitations for auction execution and the number of bids and resources necessitate use of a computer to perform each auction round and the entire auction consists of auction rounds sharing one or more of the following factors: common seller, common bidders, and similar resources being traded, however each auction round trades new resources. In particular, the present invention uses a computer storage with a computer-readable medium having computer code thereon for performing various computer-implemented operations necessary for timely execution of each auction in which the winners are selected not only on the basis of the bids but also on the basis of their participation in and results of previous auction rounds.
2. Description of the Related Art
An auction is a market institution with an explicit set of rules matching supplies with demands for traded resources and determining sell prices on the basis of bids from the market participants [1]. In relation to the present invention, resources include goods, services, leases, licenses, contracts, orders, or anything else which auction participants are willing to trade. In many cases, auctions will repeat frequently, either to trade a new supply of consumable resources, or to trade a new period of time for reusable resources or for other relevant reasons.
For direct auctions, purchasers are termed bidders, and the seller or sellers are termed the auctioneer. For reverse auctions, the purchasers are termed the auctioneer and sellers are termed bidders. The present invention applies irrespective of whether the participants (bidders and auctioneers) carry out their roles directly, through an agent, or using an automated program, and also irrespective of whether the participants (bidders and auctioneers) are individuals, legal entities, or syndicates of individuals or legal entities. Also, for the purposes of this document a “higher” bid is defined as one more advantageous to the auctioneer, i.e., a higher bid for purchasing a resource in direct auctions and a lower bid for selling a resource in reverse auctions.
Participants' bids are dependent on their respective resource valuation that may vary widely across participants. When offered the resource at the price equal to his valuation, the bidder is indifferent between trading and not trading the resource. For each bidder, such valuation is called the true valuation of that bidder for the traded resource. The difference between the true valuation and the price paid for the resource defines the bidder's utility from a transaction [2]. On the other hand, the price paid by each bidder who received resources defines the revenue of the auctioneer. As a result, the total utility of an auction, that is the sum of the utilities of all bidders and the revenue of the auctioneer, is equal to the sum of the true valuations of the auction-winning bidders. Hence, one desirable property of an auction is allocating each resource to the bidder who values it the most (i.e., has the highest true valuation for this resource). This property ensures the highest possible total utility of an auction resulting in the so-called efficient auction [2]. Another important property, often related to the previous one, is to provide the incentive for the bidders to bid their true valuation, because if they do, making auction efficient is easy since the auctioneer knows the bidders true valuations from their bids.
By definition [2], the dominant strategy of each bidder is the strategy of selecting the bid that maximizes the bidder's utility from the auction. An auction mechanism that makes bidding true valuation the dominant strategy of each bidder is called incentive compatible. This is a desirable property for the auction mechanism as it enables an efficient auction and aims at maximizing the seller's revenue.
The bids entered in an auction could be either sealed (in which case, each bid is known only to the bidder issuing it and the auctioneer) or open, (in which case all bids are known to all bidders and the auctioneer). Common forms of sealed bid auctions include the First Price Sealed Bid (FPSB) auction and Second Price Sealed Bid (SPSB) auction.
In a First Price Sealed Bid (FPSB) auction, each bidder submits one sealed bid (in ignorance of all other bids) to the auctioneer. The latter determines the highest bid; the bidder with this bid receives the resource at the price equal to his bid (so in a basic FPSB auction the bid value is equal to the bid).
In a Second Price Scaled Bid (SPSB) auction, each bidder also submits one sealed bid and the bidder with the highest bid is the winner. However, the selected winner pays the price that is equal to the second-highest bid. This auction mechanism is also called the Vickrey Auction [3]. Vickery proved theoretically that the dominant strategy for each bidder is to bid his true valuation [3].
The basic auction mechanisms described above have been generalized in many directions. In a Multi-attribute Auction (MA), the auctioneer selects winners based on a bid as well as on various other attributes, some of which may be a component of the bid (such as a proposed settlement time), while others may be properties of the bidder. A generic procedure for selecting winners in a multi-attribute auction in electronic procurement environments is presented in [4, 5]. The utility function of a Multi-attribute Auction is based on Multi-Attribute Utility Theory (MAUT) [6, 7].
Combinatorial Auctions allow each bidder to offer a bid for a collection of goods (of the bidder's choosing) rather than placing a bid on each resource separately. This enables the bidder to express dependencies and complementarities between goods. The auctioneer selects such set of these combinatorial bids that results in the largest revenue without assigning any object to more than one bidder. However, determining the set of winners of the auction that maximizes the revenue for large numbers of bids is computationally very intensive (more precisely, it is an NP-complete problem [8, 9]). Under certain restrictions, such as a limited number of bids, an efficient solution is possible [8]. An auction house with a generalized combinatorial auction is described in [10].
The Vickrey Auction has also been generalized to the case in which there are multiple units of a resource [11]. The so-called Generalized Vickrey Auction (GVA) mechanism determines the allocation of multiple units of a resource to the bidders in a way that makes the auction incentive compatible but finding such allocation is computationally intense (NP-complete [11]).
In the current state of the art, all auction systems can be generalized into the six-step process as described below and depicted in FIG. 1.
The bid collection and validation procedure collects the bids from the users participating in the market. This component can be represented by a human agent or can be embedded in a computer system. Bids may be firm (not revisable or cancelable) or changeable under predefined rules. In the case of combinatorial auctions, bids will also contain additional contingent characteristics. Furthermore, bids may or may not roll over into the next auction round under pre-specified rules or may be conditional upon specific conditions being met. Such factors can be defined in arbitrary ways by the auctioneer based upon what is deemed suitable for the specific application. Any set of predefined rules can be used for eligibility of the bid and bidder to participate in the relevant auction round, including, but not limited to, legal restrictions, credit limits on particular bidders, minimum/maximum bid amounts and sizes, etc. Cancellation of bids that do not meet such requirements comprises the validation stage of the process.
An auction round close occurs once a specific set of circumstances are met, as defined by the auctioneer. These could include the availability of the resource, time elapsed since the preceding auction round close, receipt of sufficient number of bids, or any other conditions relevant to the specific application. Once an auction round closes, further computation occurs and bids would not be changeable or revocable. The time between when one auction round closes and the next one opens for bids can also be defined arbitrarily or by specific relevant conditions.
The valuation and bid ranking procedure operates after the auction round closes. The bid ranking procedure computes the bid value for each bid collected and eligible for participation according to any specific rules set. The most basic auction mechanisms equate the bid value with the bid itself. A lot of innovation went into providing more subtle bid valuation methods, reflecting additional features. In multi-attribute auctions, multiple attributes of the bid are combined into a single bid value [4]. One example of assigning bid value on a basis other than just a bid arises in Internet search pay-per-click advertising auctions in which a bid value is the product of the bid and click-through rate [12]. Other potential methods for assigning a value to a bid by the given bidder include additional information about the bid and the bidders, such as the time of the bid, geographical location of the bidders, etc. The final result of this procedure is the list of bidders ranked according to the values assigned to their bids. The present invention is applicable to any specific valuation and bid ranking procedure.
In the resource collection and ranking procedure, all resources available for allocation in the given round are ranked according to their intrinsic values, usually established by the auctioneer. A resource can be placed in an arbitrary order with respect to resources from which its intrinsic value cannot be differentiated. The resulting rankings may be collected in human accessible media (e.g., a printed list, list displayed on a screen etc.) or created in computer-assisted media to ensure timely and efficient processing of the information. Any relevant factors can be used to assign intrinsic value rank to the resources, as deemed appropriate to the specific application. Generally, the ranking reflects differences in intrinsic values of each individual unit of the resource. For example, value and therefore ranking of seats at the theater could be differentiated based on the distance from and the visibility of the stage. Likewise, the value and therefore ranking in Internet search pay-per-click advertisements is differentiated based on the position of the advertisement link on an Internet search query page [12].
The winner selection step takes each winner and establishes the mapping of bidders to resources. Traditional auction mechanisms map the bidder ranked k=1, 2, . . . up to the number of resources available, to the resource of the same rank.
The final step, pricing method computes the price to be paid by each bidder that receives a resource. The two main variants of pricing method step in the current state of the art are to pay the price equal to either own bid (FPSB) or the bid of the next highest bidder (SPSB). In the case where the bidders are ranked using other features in addition to the bid, the SPSB guarantees that the price paid by the bidder does not exceed the own bid of such bidder.
There may be additional contingencies which govern the exact amount of the final payment or whether there is to be any payment, such as whether the resource is fully utilized, delivered in accordance to preset terms, or other predefined rules. For instance, in commodities futures markets, different quality grades of the same resource have a fixed discount or premium to the basic price when they are delivered at expiry. Another example is Internet search pay-per-click advertisements, in which the final payment to the auctioneer is only triggered if a third party clicks on such advertisement.
Recurring auctions are increasingly popular form of markets for resources including but not limited to perishable goods (fresh flowers that wilt, fresh food that spoils and Internet search pay-per-click advertisements that appear only once immediately after a search query, etc,) and services for a specific time period (e.g., ticket for a designated flight, a specific concert, computer network bandwidth allocation for predefined period of time or parking spot reservation for the specific time, as well as leases). Traditional auctions strive to motivate bidders to bid their true valuation of the resources traded. Yet, when successful in that respect, they also quickly divide the bidders into permanent winners (those with high true valuation of the traded resources) and permanent losers (those with low true valuation for the traded resources). In a recurring auction, the latter have no incentive to stay in future auction rounds, as they repeatedly lose the desired resource for which they are bidding. As a result, sooner or later, permanent losers of previous auction rounds drop out of the future rounds of a recurring auction. For purposes of the present invention, this phenomenon is referred to as a bidder drop. The bidder drop decreases the competitive pressure and therefore depresses the bids entered in future auction rounds [13].